package cn.djb.day4;


/**
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution_3 {

    /**
     * 二分法 left right
     * 比较 数值与该下标
     * value = index   left = index+1
     * value > index   right = index-1
     * 不存在 value < index   right = index-1
     *
     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {
        int left = 0, right = nums.length-1;

        while (left <= right) {
            int m = (left + right) / 2;
            int tmp = nums[m];
            if (tmp == m) left = m + 1;
            else right = m - 1;
        }
        return left;

    }
}